package main

func isPalindrome(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}
	middle := middleOfList(head)

	left := head
	right := reverse(middle)

	for right != nil {
		if left.Val != right.Val {
			return false
		}

		left = left.Next
		right = right.Next
	}

	return true
}

func middleOfList(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	// length is odd
	// slow pointer should move forward by one step
	// 1 -> 2 -> 3 -> 2 -> 1
	//           slow         fast
	if fast != nil {
		slow = slow.Next
	}

	return slow
}

func reverse(head *ListNode) *ListNode {
	var prev *ListNode
	cur := head

	for cur != nil {
		next := cur.Next
		cur.Next = prev
		prev = cur
		cur = next
	}

	return prev
}
